When an electronic system includes multiple local memories, such as local cache memories, servicing of access requests to the multiple local memories needs to be maintained. This servicing of access requests typically includes sending a message indicating that a request to access a particular location in a memory device cannot be serviced and should be retried at a future time. As the number of local memory devices and/or processors increases, the problem of these “retried” access requests also increases.
The cache memory in multiprocessor systems may be kept coherent using a snoopy bus or a directory based protocol. In either case, a memory address is associated with a particular location in the system. This location is known as the “home node” of the memory address. In a directory based protocol, multiple processing/caching agents may concurrently make requests to the home node for access to the same memory address with which the home agent is associated. “Target node” refers to a node which is the target of a request to access a location in memory associated with the node. A node sending such a request is a “source node”. The mechanism for handling the request at a node is the agent of the node. The target agent processes such requests using a finite number of resources, which are occupied while processing a request and released when processing the request is completed. If there is no resource available at the target agent, the request is “retried” by the source agent in response to a message sent indicating the need to retry the access request later. The request may also be retried if there is a conflicting request for the same memory address being processed at the target agent.
For those cache coherency protocols that allow retries of requests, it is possible that a request from one source agent encounters either a conflict or an unavailability of appropriate resources every time it is retried to the target. The result is that the request from that source agent is never serviced by the target agent. This failure to service a request is referred to as “starvation”, and may result in a livelock in the system. In a livelock situation, some agents are either unable to complete their transactions or keep repeating the same operation without making progress. In the interest of system performance, it is critical to have a fair servicing mechanism that ensures forward progress in processing requests from multiple agents.